#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

//#define HOUYI_DEBUG
#define HOUYI_IMPLEMENTATION
#include "houyi.h"

static void prefix_function(void);
static void postfix_function(void);

#define TEST_INIT prefix_function()
#define TEST_FINI postfix_function()
#include "acutest.h"

#ifndef UNUSED
#define UNUSED(X) ((void)X)
#endif

static char error_string[256];
static void test_err_handler(const char *file, const int line, const char *error_message);

static void prefix_function(void)
{
    memset(error_string, 0, sizeof(error_string));
    houyi_error_handler = test_err_handler;
}

static void postfix_function(void)
{
}

static bool iterator_cb(houyi_key_t key, houyi_value_t value, houyi_iter_data_t idata)
{
    printf("\n%s->%s (%p)", (char*)key, (char*)value, idata);
    return false;
}

static const houyi_init_t default_init = {
    .capacity = 100,
    .store = NULL,
    .seed = 0xdeadbabe,
    .skey = 0,      // the key is a string
    .svalue = 0,    // the value is also a string
    .max_load = 0,  // the maximum load factor (using default: 0.7)
    .hasher = NULL,
    .fkeq = NULL,
    .falloc = NULL,
    .dealloc = NULL,
};

// the selected vectors are just a simple sanity test that FNV-1a is probably correctly implemented
// the vectors will be expanded should it prove that more testing of the hash function is required (unlikely)
#define R10(X)    X X X X X X X X X X
#define R100(X)   R10(X)R10(X)R10(X)R10(X)R10(X)R10(X)R10(X)R10(X)R10(X)R10(X)
#define R500(X)   R100(X)R100(X)R100(X)R100(X)R100(X)
#define VS(X,H)   X,sizeof(X)-1,H
#define VB(X,H)   X,sizeof(X)  ,H
typedef struct test_vector_t
{
    const char     *vector;
    const size_t    size;
    const uint32_t  hash;
} test_vector_t;
const test_vector_t vectors[] = {
    { VS("", 0x811c9dc5UL) },
    { VS("a", 0xe40c292cUL) },
    { VS("fooba", 0x39aaa18aUL) },
    { VS("foobar", 0xbf9cf968UL) },
    { VB("foo", 0x6150ac75UL) },
    { VB("foob", 0x9aab3a3dUL) },
    { VS("chongo w", 0xdd77ed30UL) },
    { VS("chongo wa", 0xf4ca9683UL) },
    { VB("ch", 0x1c85c7caUL) },
    { VB("cho", 0x0229fe89UL) },
    { VB("chongo was h", 0x5a740578UL) },
    { VB("chongo was he", 0x5b004d15UL) },
    { VS("curds ", 0xd5c428d0UL) },
    { VS("curds a", 0x34cc0ea3UL) },
    { VB("cu", 0x4a56b1ffUL) },
    { VB("cur", 0x70b8e86fUL) },
    { VB("curds and wh", 0x2183ff1cUL) },
    { VB("curds and whe", 0x2bd54279UL) },
    { VS("\xff\x00\x00\x02", 0xc18fb3b4UL) },
    { VS("\x02\x00\x00\xff", 0x50ef1236UL) },
    { VS("\x40\x51\x4e\x54", 0x4217a988UL) },
    { VS("\x54\x4e\x51\x40", 0x772633d6UL) },
    { VS("64.81.78.74", 0x1353e852UL) },
    { VB("64.81.78.74", 0xbf16b916UL) },
    { VS("line 1\nline 2\nline 3", 0x97b4ea23UL) },
    { VS("chongo <Landon Curt Noll> /\\../\\", 0x9a4e92e6UL) },
    { VS("http://hvo.wr.usgs.gov/cams/HMcam/", 0xc9302890UL) },
    { VS("http://hvo.wr.usgs.gov/kilauea/update/deformation.html", 0x956ded32UL) },
    { VS("http://volcano.wr.usgs.gov/kilaueastatus.php", 0x7837b203UL) },
    { VS("http://www.avo.alaska.edu/activity/Redoubt.php", 0x319e877bUL) },
    { VS("http://www.isthe.com/chongo/tech/astro/venus2004.html", 0x76966481UL) },
    { VS("http://www.isthe.com/chongo/tech/astro/vita.html", 0x063258b0UL) },
    { VS("http://www.lavarnd.org/cgi-bin/haiku.cgi", 0x91f8f676UL) },
    { VS("http://www.lavarnd.org/cgi-bin/rand-none.cgi", 0x0bf58848UL) },
    { VS("http://www.sciencenews.org/index/home/activity/view", 0x2fe1b574UL) },
    { VS("http://www.skyandtelescope.com/", 0xcf0cd31eUL) },
    { VS(R10("\x54\xc5"), 0x241e9075UL) },
    { VS(R10("\xc5\x54"), 0x063f70ddUL) },
    { VS(R10("FEDCBA9876543210"), 0xf3415c85UL) },
    { VS(R10("\xfe\xdc\xba\x98\x76\x54\x32\x10"), 0x0ae4ff65UL) },
    { VS(R500("\x7f"), 0x813b0881UL) },
    // terminating record
    { NULL, 0, 0 },
};

#define SKV(K, V) { K, V, strlen(K), strlen(V), }
static const struct {
    void *key;
    void *value;
    size_t ksize;
    size_t vsize;
} skvpairs[] = {
    SKV("key001", "val001"), SKV("key002", "val002"), SKV("key003", "val003"),
    SKV("key004", "val004"), SKV("key005", "val005"), SKV("key006", "val006"),
    SKV("key007", "val007"), SKV("key008", "val008"), SKV("key009", "val009"),
    SKV("key010", "val010"), SKV("key011", "val011"), SKV("key012", "val012"),
    SKV("key013", "val013"), SKV("key014", "val014"), SKV("key015", "val015"),
    SKV("key016", "val016"), SKV("key017", "val017"), SKV("key018", "val018"),
    SKV("key019", "val019"), SKV("key020", "val020"), SKV("key021", "val021"),
    SKV("key022", "val022"), SKV("key023", "val023"), SKV("key024", "val024"),
    SKV("key025", "val025"), SKV("key026", "val026"), SKV("key027", "val027"),
    SKV("key028", "val028"), SKV("key029", "val029"), SKV("key030", "val030"),
    SKV("key031", "val031"), SKV("key032", "val032"), SKV("key033", "val033"),
    SKV("key034", "val034"), SKV("key035", "val035"), SKV("key036", "val036"),
    SKV("key037", "val037"), SKV("key038", "val038"), SKV("key039", "val039"),
    SKV("key040", "val040"), SKV("key041", "val041"), SKV("key042", "val042"),
    SKV("key043", "val043"), SKV("key044", "val044"), SKV("key045", "val045"),
    SKV("key046", "val046"), SKV("key047", "val047"), SKV("key048", "val048"),
    SKV("key049", "val049"), SKV("key050", "val050"), SKV("key051", "val051"),
    SKV("key052", "val052"), SKV("key053", "val053"), SKV("key054", "val054"),
    SKV("key055", "val055"), SKV("key056", "val056"), SKV("key057", "val057"),
    SKV("key058", "val058"), SKV("key059", "val059"), SKV("key060", "val060"),
    SKV("key061", "val061"), SKV("key062", "val062"), SKV("key063", "val063"),
    SKV("key064", "val064"), SKV("key065", "val065"), SKV("key066", "val066"),
    SKV("key067", "val067"), SKV("key068", "val068"), SKV("key069", "val069"),
    SKV("key070", "val070"), SKV("key071", "val071"), SKV("key072", "val072"),
    SKV("key073", "val073"), SKV("key074", "val074"), SKV("key075", "val075"),
    SKV("key076", "val076"), SKV("key077", "val077"), SKV("key078", "val078"),
    SKV("key079", "val079"), SKV("key080", "val080"), SKV("key081", "val081"),
    SKV("key082", "val082"), SKV("key083", "val083"), SKV("key084", "val084"),
    SKV("key085", "val085"), SKV("key086", "val086"), SKV("key087", "val087"),
    SKV("key088", "val088"), SKV("key089", "val089"), SKV("key090", "val090"),
    SKV("key091", "val091"), SKV("key092", "val092"), SKV("key093", "val093"),
    SKV("key094", "val094"), SKV("key095", "val095"), SKV("key096", "val096"),
    SKV("key097", "val097"), SKV("key098", "val098"), SKV("key099", "val099"),
    SKV("key100", "val100"),
    // terminating record
    { NULL, NULL, 0 },
};

// note: this is not part of the public API but is done only to test
// do not do as we do
static void test_fnv1a32(void)
{
    for (size_t i = 0; vectors[i].vector; i++)
    {
        uint32_t hash = hy_fnv1a32_hash(vectors[i].vector, vectors[i].size, 0);
        TEST_CHECK_(hash == vectors[i].hash, "\"%s\": expected hash 0x%08x, calculated hash 0x%08x",
            vectors[i].vector, vectors[i].hash, hash);
    }
}

static void test_hash_mapping(void)
{
    static int counters[100];

    // count which bucket for every representative hash value
    // why increment 211?: it's coprime to 0xffffffff
    for (size_t i = 0; i < 0xffffffff; i += 211)
    {
        TEST_CASE_("Hash: 0x%08lx", i);
        int bucket = hy_hash_to_index(i, 100);
        TEST_CHECK_((bucket >= 0) && (bucket < 100), "index out of range (%d) for hash 0x%08lx", bucket, i);
        counters[bucket]++;
    }

    // check that hashes are evenly distributed:
    for (size_t i = 0; i < 100; i++)
    {
        // the counters are calculated:
        // 0xffffffff / buckets (100) / step (211) which is about 203552.95
        // thus the count of each bucket, if the spread is even, should be 203552 or 203553
        TEST_CHECK_((counters[i] == 203552) || (counters[i] == 203553), "failure: %ld -> %d", i, counters[i]);
    }
}

void test_init_delete(void)
{
    houyi_init_t init = default_init;

    void *h = houyi_init(init);
    hy_table_t *t = h;

    TEST_CHECK(t->capacity == init.capacity);
    TEST_CHECK(t->hashes != NULL);

    uintptr_t store = (uintptr_t)t->hashes;
    TEST_CHECK(t->lprobes == (size_t *)(store + 100 * sizeof(t->hashes[0])));
    store = (uintptr_t)t->lprobes;
    TEST_CHECK(t->keys == (void **)(store + 100 * sizeof(t->lprobes[0])));
    store = (uintptr_t)t->keys;
    TEST_CHECK(t->values == (void **)(store + 100 * sizeof(t->keys[0])));

    TEST_CHECK(t->dynamic == true);
    TEST_CHECK(t->count == 0);
    TEST_CHECK(t->skey == init.skey);
    TEST_CHECK(t->svalue == init.svalue);
    TEST_CHECK(t->seed == init.seed);
    TEST_CHECK(t->max_load == 0.7); // we selected default, and that's 0.7

    TEST_CHECK(t->fhash == hy_fnv1a32_hash);
    TEST_CHECK(t->fkeq == hy_equals);
    TEST_CHECK(t->falloc == calloc);
    TEST_CHECK(t->fdealloc == free);

    houyi_delete(h);
}

void test_string_insertion(void)
{
    houyi_init_t init = default_init;

    void *h = houyi_init(init);
    hy_table_t *t = h;

    for (int kv = 0; skvpairs[kv].key != NULL; kv++)
    {
        TEST_CHECK(t->count == kv);
        houyi_error_t err = houyi_insert(h, skvpairs[kv].key, skvpairs[kv].value);
        TEST_CHECK(err);
        TEST_CHECK(t->count == kv + 1);

        int idx = hy_find_key(h, skvpairs[kv].key);
        TEST_CHECK(idx != -1);

        TEST_CASE_("kv = %d, key = %s, value = %s, idx = %d",
            kv, (char*)skvpairs[kv].key, (char*)skvpairs[kv].value, idx);

        TEST_CHECK(err == ((kv >= 69) ? (HOUYI_LOAD_FACTOR) : (HOUYI_SUCCEED)));
        houyi_hash_t chash = hy_fnv1a32_hash(t->keys[idx], strlen(t->keys[idx]), t->seed);
        TEST_ASSERT_(t->hashes[idx] == chash, "expected 0x%08x, got 0x%08x", chash, t->hashes[idx]);
        TEST_CHECK(houyi_has(h, skvpairs[kv].key));

        TEST_CHECK(memcmp(t->keys[idx], skvpairs[kv].key, skvpairs[kv].ksize) == 0);
        TEST_CHECK(memcmp(t->values[idx], skvpairs[kv].value, skvpairs[kv].vsize) == 0);

        double lf = houyi_load_factor(h);
        double clf = (double)(kv + 1) / houyi_capacity(h);
        TEST_CHECK(lf >= clf && lf <= clf);
    }

    houyi_dump_table(h);
    // And now for an insertion that *must* fail...
    TEST_CHECK(!houyi_insert(h, "hello", "goodbye"));
    TEST_CHECK(!houyi_has(h, "hello"));

    houyi_delete(h);
}

void test_key_removal(void)
{
    houyi_init_t init = default_init;

    void *h = houyi_init(init);

    /* fill a table to the default load factor */
    /* this should get us some collisions, etc. */
    houyi_error_t err = HOUYI_SUCCEED;
    for (int kv = 0; err != HOUYI_LOAD_FACTOR; kv++)
    {
        err = houyi_insert(h, skvpairs[kv].key, skvpairs[kv].value);
        TEST_CHECK(err);
    }
    TEST_CHECK(houyi_load_factor(h) == 0.7);
    TEST_CHECK(houyi_count(h) == 70);

    TEST_CHECK(houyi_iteration_prep(h, NULL) == HOUYI_SUCCEED);
    TEST_CHECK(houyi_iterate(h, iterator_cb) == HOUYI_SUCCEED);

    size_t max = houyi_count(h);
    size_t count = max;
    for (size_t i = 0; i < max; i++, count--)
    {
        TEST_CHECK_(houyi_count(h) == count, "%ld: count should have been %ld, was %ld", i, count, houyi_count(h));
        TEST_CHECK(houyi_has(h, skvpairs[i].key) == HOUYI_SUCCEED);
        err = houyi_remove(h, skvpairs[i].key, NULL);
        TEST_CHECK(err);
        TEST_CHECK(err != HOUYI_KEY_NOT_FOUND);
        TEST_CHECK(houyi_has(h, skvpairs[i].key) == HOUYI_FAIL);
    }

    houyi_delete(h);
}

static void test_err_handler(const char *file, const int line, const char *error_message)
{
    sprintf(error_string, "%s(%d): %s\n", file, line, error_message);
}

TEST_LIST =
{
    { "default hash implementation", test_fnv1a32          },
    { "hash to index mapping",       test_hash_mapping     },
    { "initialization/deletion",     test_init_delete      },
    { "inserting string k/v pairs",  test_string_insertion },
    { "key removal",                 test_key_removal      },

    { NULL, NULL },
};
